package dicTree;

public class DesignAddAndSearchWordsDataStructure211 {
    TrieTree root;
    public DesignAddAndSearchWordsDataStructure211() {
         root = new TrieTree();
    }

    public void addWord(String word) {
        root.addWord(word);
    }

    public boolean search(String word) {
        return root.search(word,0,root);
    }


    class TrieTree {
        boolean isEnd;
        TrieTree[] childs;

        public TrieTree() {
            isEnd = false;
            childs = new TrieTree[26];
        }

        public void addWord(String word) {
            TrieTree cur = this;
            for (char c : word.toCharArray()
            ) {
                if (cur.childs[c - 'a'] == null) {
                    cur.childs[c - 'a'] = new TrieTree();
                }
                cur = cur.childs[c - 'a'];
            }
            cur.isEnd = true;
        }

        public boolean search(String word, int index, TrieTree trieTree) {
            if(index==word.length()){
                return trieTree.isEnd;
            }
            if(trieTree==null){
                return false;
            }
            char c = word.charAt(index);
            if (c == '.') {
                for (int i = 0; i < trieTree.childs.length; i++) {
                    if(trieTree.childs[i]!=null&&search(word,index+1,trieTree.childs[i])){
                        return true;
                    }
                }
                return false;
            } else {
                if(trieTree.childs[c-'a']==null){
                    return false;
                }else {
                    return search(word, index+1, trieTree.childs[c-'a']);
                }
            }

        }
    }
}
